1. Field of the Invention
The present invention relates to the data replication methods which provide high data availability for disk arrays.
2. Related Art
Recent advances on multimedia technologies have led to the creation of several new application in both information providing services and the entertainment business. Given the extremely large data size, one of the major challenges in the handling of multimedia data is to support very high disk bandwidth for video data retrieval. For example, the displaying HDTV quality image may require data rate of 2-3 Mbyte per second (after compression). In general, it is very undesirable to store such a large video in a single disk for the following reasons: First, a 100-minute HDTV movie will require more than 12-Gbyte storage. Such a large disk is usually expensive. Second, playing a hot (i.e., frequently requested) movie by a single disk will cause performance bottleneck. In fact, even for playing ordinary MPEG movies, the need to support multiple video streams by a video server also calls for the use of disk-arrays. Consequently, it is highly desirable to use disk arrays to handle the storage and retrieval of multimedia data.
Various studies have been conducted to evaluate and to enhance the performance of disk arrays. The issue of data availability assumes an even greater importance for real-time applications such as video-on-demand (VOD). However, as the number of disks used in the a disk array increases, the probability of disk failures increases. It has been projected that the average disk array installation in a VOD system will have 50,000 drives, each of which has a capacity of 200 MB, by the year of 2000. With 1000 installations, the projected mean-time-to-data-loss (MTTDL) is approximately 460 hours, or just 20 days. As a result, it has become necessary to devise effective methods to recover from disk failures on-line for the high data availability required for years to come. The replication approach, which stores multiple copies of data in different disks, is generally preferable for real-time applications to achieve fault-tolerance. In a VOD environment, usually most of the requests are for a small number of hot videos. Hence, the replication approach is used to selectively replicate the hot videos so that the service rate can be maintained upon disk failures.
There have been a number of prior art techniques proposed to explore the replication approach. These techniques differ in their ability to handle access skew, to service multiple request sizes, and to redistribute workload after failures. Basically, there are two data declustering techniques: mirrored declustering and chained declustering.
In mirrored declustering, the disks are organized into a set of identical pairs. The mirrored declustering strategy allows for the spreading of relations over multiple disks, while maintaining the mirrored disk tuples. In accordance with generalized mirrored declustering, in a cluster of rn disks numbered 0, 1, . . . , rn-1, the i.sup.th partition of j.sup.th replica (i.ltoreq.j.ltoreq.r) is placed on disk (i mod n)+(j-1) * n. An illustrative example is given in Table 1, where the data blocks are labeled d0-d7, r=2, n=4 and the number of disks in the disk array is rn=8.
TABLE 1 ______________________________________ A double redundant disk array with mirrored declustering Disk 0 1 2 3 4 5 6 7 ______________________________________ d0-d3 d0 d1 d2 d3 d0 d1 d2 d3 d4-d7 d4 d5 d6 d7 d4 d5 d6 d7 ______________________________________
In chained declustering, the primary data copy in disk i has a backup copy in disk (i+1) mod n, where n is the number of disks in the disk array. Note that the cluster size for data placement in the chained declustering could be different from the disk array size, and explicitly, is only required to be a sub-multiple of the disk array size. A disk array based on chained declustering with the cluster size equal to 4 is shown in Table 2.
TABLE 2 ______________________________________ Chained declustering disk array with double redundancy Disk 0 1 2 3 4 5 6 7 ______________________________________ 1st Copy d0 d1 d2 d3 d4 d5 d6 d7 2nd Copy d3 d0 d1 d2 d7 d4 d5 d6 ______________________________________
In the presence of disk failures, the chained declustering method is able to achieve better fault-tolerance and load balancing than the mirrored declustering method. On the other hand, the latter method has better flexibility than the former in dynamically adding or dropping data copies. Note that in some real-time applications such as VOD, the number of copies stored for a video (e.g. a movie) will change as the demand for the video changes. Chained declustering, under which adding/dropping data copies requires interrupting on-line execution, is thus unfavorable for such applications.